(0) Obligation:
Runtime Complexity Relative TRS:
The TRS R consists of the following rules:
merge(Cons(x, xs), Nil) → Cons(x, xs)
merge(Cons(x', xs'), Cons(x, xs)) → merge[Ite](<=(x', x), Cons(x', xs'), Cons(x, xs))
merge(Nil, ys) → ys
goal(xs, ys) → merge(xs, ys)
The (relative) TRS S consists of the following rules:
<=(S(x), S(y)) → <=(x, y)
<=(0, y) → True
<=(S(x), 0) → False
merge[Ite](False, xs', Cons(x, xs)) → Cons(x, merge(xs', xs))
merge[Ite](True, Cons(x, xs), ys) → Cons(x, merge(xs, ys))
Rewrite Strategy: INNERMOST
(1) DecreasingLoopProof (EQUIVALENT transformation)
The following loop(s) give(s) rise to the lower bound Ω(n1):
The rewrite sequence
merge(Cons(0, xs'), Cons(x, xs)) →+ Cons(0, merge(xs', Cons(x, xs)))
gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
The pumping substitution is [xs' / Cons(0, xs')].
The result substitution is [ ].
(2) BOUNDS(n^1, INF)